// RTS sample program

#include "rts.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e5+10;
const int inf = 0x3f3f3f3f;

struct edge{int v,nxt;}e[MAXN<<1];
int v[MAXN],tim,n,fa[MAXN],rt,SIZ,MX,root=1,siz[MAXN],son[MAXN],p[MAXN],cnt = 1,h[MAXN];
bool vis[MAXN],del[MAXN];
double al = 0.75;

void link(int x,int y){e[++cnt] = (edge){y,h[x]};h[x] = cnt;}

namespace chain{
	void work(){
		int L = 1,R = 1;
		for(int i = 1;i < n;i++){
			if(vis[p[i]]) continue;
			int x = p[i],y = explore(L,x);
			if(!vis[y]) L = x,vis[y] = 1;
			else y = R,R = x;
			while(y != x) y = explore(y,x),vis[y] = 1;
		}
	}
}

void clear(int x,int f){
	del[x] = 0;
	for(int i = h[x];i;i = e[i].nxt){
		int y = e[i].v; if(y == f || v[y] == tim) continue;
		clear(y,x);
	}
}

void getroot(int x,int f){
	son[x] = 0,siz[x] = 1;
	for(int i = h[x];i;i = e[i].nxt){
		int y = e[i].v;if(y == f || v[y] == tim) continue;
		getroot(y,x); siz[x] += siz[y]; son[x] = max(son[x],siz[y]);
	}
	son[x] = max(son[x],SIZ - siz[x]);
	if(son[x] < MX) rt = x,MX = son[x];
}

void divide(int x){
	v[x] = tim;
	for(int i = h[x];i;i = e[i].nxt){
		int y = e[i].v;if(v[y] == tim) continue;
		SIZ = siz[y];MX = inf,rt = 0;getroot(y,0);
		siz[rt] = siz[y];fa[rt] = x; divide(rt);
	}
}

void rebuild(int x){
	++tim; for(int i = fa[x];i;i = fa[i]) v[i] = tim; clear(x,0);
	SIZ = siz[x]; MX = inf; rt = 0; getroot(x,0);
	if(x == root) root = rt; siz[rt] = siz[x];fa[rt] = fa[x]; divide(rt);
}

void update(int x){
	if(!fa[x]) {if(del[x]) rebuild(x);return;}
	siz[fa[x]]++;if(al * siz[fa[x]] < siz[x]) del[fa[x]] = 1;
	update(fa[x]); if(del[x]) rebuild(x);
}

void Find(int x){
	int u = root;
	while(!vis[x]){
		int y = explore(u,x);
		if(vis[y]) {while(fa[y] != u) y = fa[y];u = y;}
		else{link(y,u),link(u,y),siz[y] = 1,fa[y] = u,update(y),u = y,vis[y] = 1;}
	}
}

void play(int nn, int T, int dataType) {
	n = nn;vis[1] = 1;for(int i = 2;i <= n;i++) p[i-1] = i;
	random_shuffle(p+1,p+n);if(dataType == 3) chain::work();
	else for(int i = 1;i < n;i++) if(!vis[p[i]]) Find(p[i]);
}
